//
//  RemoveBoxes.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/8/15.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  546. 移除盒子

import UIKit

/*
 546. 移除盒子
 
 给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。
 你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。
 当你将所有盒子都去掉之后，求你能获得的最大积分和。

  

 示例：

 输入：boxes = [1,3,2,2,2,3,4,3,1]
 输出：23
 解释：
 [1, 3, 2, 2, 2, 3, 4, 3, 1]
 ----> [1, 3, 3, 4, 3, 1] (3*3=9 分)
 ----> [1, 3, 3, 3, 1] (1*1=1 分)
 ----> [1, 1] (3*3=9 分)
 ----> [] (2*2=4 分)
 */

class RemoveBoxes: NSObject {
    func removeBoxes(_ boxes: [Int]) -> Int {
    
        let dp = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: -1, count: 100), count: 100), count: 100)
        
        return self.helper(boxes, dp, 0, boxes.count - 1,  0)
    }
    

    func helper(_ boxes: [Int], _ dp: [[[Int]]], _ l : Int, _ r: Int, _ k: Int) -> Int{
        if l > r {
            return 0
        }
        if dp[l][r][k] != 0{
            return dp[l][r][k]
        }
        
        let l = l
        var r = r
        var k = k
        var dp = dp
        while r > l && boxes[r] == boxes[r-1] {
            r -= 1
            k += 1
        }
        
        dp[l][r][k] = self.helper(boxes, dp, l, r-1, 0) + (k + 1)*(k + 1)
        for i in l ..< r{
            if boxes[i] == boxes[r]{
                dp[l][r][k] = max(dp[l][r][k], self.helper(boxes, dp, l, i, k+1) + self.helper(boxes, dp, i+1, r-1, 0))
            }
        }
        return dp[l][r][k]
    }
    
}
